package com.tgy.leetcode;

/**
 * @Author: tgy
 * @Date: 2020-11-03 13:42
 *
 * https://leetcode-cn.com/problems/trapping-rain-water/
 */
public class _42_接雨水 {

    public int trap(int[] height) {

        if (height.length <= 2) {

            return 0;
        }

        int index = maxIndex(height, 0, height.length);
        return findLeftWater(height,index) + findRightWater(height,index);

    }

    private int maxIndex(int[] height, int begin,int end) {

        int index = begin;

        for (int i = begin + 1; i < end ; i++) {

            if (height[i] > height[index]) {

                index = i;
            }
        }

        return index;
    }


    private int findLeftWater(int [] height, int maxIndex) {

        if (maxIndex <= 1) {

            return 0;
        }

        int index = maxIndex(height, 0, maxIndex);

        int water = 0;
        for (int i = index + 1; i < maxIndex; i++) {

            water += (height[index] - height[i]);
        }

        int leftWater = findLeftWater(height, index);

        return water + leftWater;
    }

    private int findRightWater(int[]height, int maxIndex) {

        if (maxIndex >= height.length - 2) {

            return 0;
        }

        int index = maxIndex(height, maxIndex + 1, height.length);

        int water = 0;
        for (int i = maxIndex + 1; i < index ; i++) {

            water += (height[index] - height[i]);
        }

        return water + findRightWater(height,index);
    }
}
